#pragma once

#include <string>
#include <vector>
#include <stack>
#include <unordered_map>

#include "ResultGraphTableNode.h"
#include "Table.h"
#include "RelationshipType.h"
#include "PKB.h"
#include "SynonymTable.h"

class ResultGraphTable {

private:
	static std::string ANY_SYNONYM;

	struct edge {
		const ResultGraphTableNode* leftNode;
		const ResultGraphTableNode* rightNode;
	};
	
	typedef Table<std::string, int> SynonymResultsTable;

	typedef std::unordered_map<string, ResultGraphTableNode*> NodeMap; // keyed by nodeId
	typedef std::unordered_map<string, edge> EdgeMap; // keyed by edgeId
	typedef std::unordered_map<string, EdgeMap*> EdgeMapsBySynonymName; // keyed by synonymName
	typedef std::unordered_map<string, int> NodeCountMap; // keyed by synonymName
	typedef std::unordered_map<string, int> EdgeCountMap; // keyed by synonymName
	// PathMap is std::unordered_map<string currentSynonym, string nextSynonymToGoTo>
	// used in findPathFromSynonymToSynonym()
	typedef std::unordered_map<string, string> PathMap;
	// A BadEdgesMap, used to say if an edge is bad or not.
	// This is used during tuple-finding to ensure that bad edges
	// are not traversed.
	// Whenever we performTraversalForRelationshipEvaluation,
	// BadEdgeMaps are created for each node if not existing in the BadEdgeMapPtrs.
	// Keyed by edgeId.
	typedef std::unordered_map<string, bool> BadEdgeMap; 
	// BadEdgeMapPtrs keyed by the node id.
	typedef std::unordered_map<string, BadEdgeMap*> BadEdgeMapPtrs;
	typedef std::unordered_map<const ResultGraphTableNode*, bool> BadEdgeCheckingNodeMap;
	// Keyed by the node id
	typedef std::unordered_map<string, BadEdgeCheckingNodeMap*> BadEdgeCheckingNodeMapPtrMap;

	// Column headers, indexed by the synonym e.g. "v"
	// unordered_map<synonymName, headerNode>
	std::unordered_map<std::string, ResultGraphTableNode*> mHeaders;
	// The columns themselves, indexed by the synonym e.g. "v"
	// unordered_map<synonymName, unordered_map<nodeId, node>>
	std::unordered_map<std::string, NodeMap*> mColumns;
	// Node-to-list of edges unordered_mapping so as to find list of edges for a node quickly, indexed by the node identifier
	// unordered_map<nodeId, unordered_map<edgeId, edge>>
	// unordered_map<nodeId, unordered_map<synonymName, unordered_map<edgeId, edge>>>
	std::unordered_map<std::string, EdgeMapsBySynonymName*> mEdges;
	// Maps a unordered_map of the count of adjacent nodes keyed by synonymName2, keyed by synonymName1.
	// unordered_map<synonym1, unordered_map<synonymName2, edgeCount>>
	// Answers the question: how many edges are there directly connecting nodes of synonymName1 and nodes of synonymName2?
	std::unordered_map<std::string, EdgeCountMap*> mAdjacentEdgeCountMap;
	// Maps a unordered_map of the count of adjacent nodes indexed by synonymName, indexed by the nodeIdentifier
	// unordered_map<nodeId, unordered_map<synonymName, nodeCount>>
	std::unordered_map<std::string, NodeCountMap*> mAdjacentNodeCountMap;
	// Used when finding tuples. Contains information about
	// what are the bad edges (edges to NOT traverse) when finding tuples,
	// for a given starting node. Keyed by node id. Indexes with a BadEdgeMap* for that node.
	BadEdgeMapPtrs mBadEdgeMapPtrs;
	BadEdgeMapPtrs mGoodEdgeMapPtrs;
	// Used when finding tuples. Contains information about
	// which nodes we should check for bad edges when finding tuples.
	// Keyed by node id. Indexes with a BadEdgeCheckingNodePtrMap* for that node.
	BadEdgeCheckingNodeMapPtrMap mBadEdgeCheckingNodeMapPtrMap;

	void ResultGraphTable::performTraversalForRelationshipEvaluation(PKB *pkb, SynonymTable *synonymTable,
		RelationshipType relType, const std::string& synonym1, const std::string& synonym2, 
		const ResultGraphTableNode * const startingNode, const ResultGraphTableNode *currentNode, 
		EdgeMap *edgesToDestroy, EdgeMap *edgesToSave, PathMap& pathMap);

	bool isSynonymRelatedToSynonym(const std::string& synonym1, const std::string& synonym2);
	// Finds a path from synonym1 to synonym2 in the graph if there exists one.
	// Returns the path in a unordered_map<currentSynonym, nextSynonymToGoTo> format, which
	// tells you which synonym to go to next if you are at currentSynonym.
	// Returns a size 0 unordered_map if there is no path to get from synonym1 to synonym2.
	PathMap& findPathFromSynonymToSynonym(const std::string& synonym1, const std::string& synonym2);
	// Initializes the column for synonymName if it doesn't already exist, and returns the pointer to the header node
	const ResultGraphTableNode& initializeColumn(const std::string& synonymName);
	// Creates an edge between the 2 specified nodes and places that edge in the list of edges for the 2 nodes in mEdges
	void linkNodes(const ResultGraphTableNode& node1, const ResultGraphTableNode& node2);
	// Adds the resultNode if it isn't already present in the column of its synonymName
	const ResultGraphTableNode* addResultNodeUniquelyToColumn(const std::string& synonymName, int nodeValue);
	// Finds, using the pkb, and returns ALL the relationship pairs for the relationship relType between synonyms 1 and 2
	std::vector<std::pair<int, std::vector<int>>>& getAllTrueRelationshipPairs(PKB *pkb, SynonymTable *synonymTable, RelationshipType relType, 
																				const std::string& synonym1, const std::string& synonym2);
	// Finds, using the pkb, and returns ALL the indexes of synonym2 for the relationship relType between 
	// the specified index synonym1Value of synonym 1 and all of synonym2
	std::vector<int>& getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(PKB *pkb, SynonymTable *synonymTable, RelationshipType relType, 
																				const std::string& synonym1, const std::string& synonym2, int synonym1Value);
	// Finds, using the pkb, and returns ALL the indexes of synonym1 for the relationship relType between 
	// all of synonym1 and the specified index synonym2Value
	std::vector<int>& getTrueRelationshipSynonym1IndexesForGivenSynonym2Index(PKB *pkb, SynonymTable *synonymTable, RelationshipType relType, 
																				const std::string& synonym1, const std::string& synonym2, int synonym2Value);
	// Finds out if, using the pkb, the relationship of relType is true between the given synonym1Value and synonym2Value
	bool checkIfIsTrueRelationship(PKB *pkb, RelationshipType relType, int synonym1Value, int synonym2Value, 
									DesignEntityType synonym1Type, DesignEntityType synonym2Type);
	// Get the list of edges of the specified node based on its node identifier and the given synonym, from mEdges
	EdgeMap* getEdgesOfNode(const ResultGraphTableNode& node, const std::string &synonym);
	// Finds all synonym1 nodes that do NOT have a DIRECT link to a synonym2 node and deletes them and their edges.
	// After deleting a node, this function also traverses all the deleted edges, attempting to find nodes which are not even indirectly
	// linked to a synonym2 node. If such nodes are found, these nodes and their edges are also deleted, and this is done recursively
	// until no more such nodes are found.
	void ensureDirectLinkRemainOnly(const std::string& synonym1, const std::string& synonym2);

	// Edge is identified by the string : (leftNodeId + rightNodeId)
	std::string getEdgeIdentifier(const edge& e);
	bool isNodeInMap(const std::unordered_map<std::string, bool>& unordered_map, const ResultGraphTableNode *node);
	bool checkEdgesHaveAtLeastOneSimilarNode(const edge& e1, const edge& e2);
	bool checkEdgesEqual(const edge& e1, const edge& e2);
	bool checkEdgeForNodeOfSynonymName(const edge& e, const std::string& synonymName);
	// Pops ALL edges from edgesStack off into the edgesVector.
	// Returns the popped edges.
	std::vector<edge>& popAllEdgesIntoUnorderedMap(std::stack<const edge*> *edgesStack, EdgeMap *edgesMap);
	// Pops edges from edgesStack off into the edgesVector, 
	// until we find a popped edge shares a similar node to the nextEdge.
	// Returns the popped edges.
	std::vector<edge>& popEdgesIntoUnorderedMapUntilSimilarNodeReached(std::stack<const edge*> *edgesStack, EdgeMap *edgesMap, const edge& nextEdge);
	// Pops nodes off the nodeStack until there is a node on either side of the nextEdge that is similar to the nextEdge to traverse
	const ResultGraphTableNode* popNodesUntilSimillarNodeReached(std::stack<const ResultGraphTableNode*> *nodeStack, const edge& nextEdge);
	const ResultGraphTableNode* popNodesUntilSimillarNodeReached(std::vector<const ResultGraphTableNode*> *nodeStack, const edge& nextEdge);
	// Returns the vector of unique edges gotten from edgesToDestroy - edgesToSave
	EdgeMap& getEdgesFromEdgesToDestroyMinusEdgesToSave(const EdgeMap& edgesToDestroy, const EdgeMap& edgesToSave);

	void destroyEdges(const EdgeMap& edgesToDestroy);
	void destroyEdge(const edge& edgeToDestroy);
	void deleteNode(const ResultGraphTableNode& nodeToDestroy);

	// Gets the count (number) of nodes of synonymName that are adjacent to the specified node
	int getCountOfAdjacentNodeOfSynonymName(const ResultGraphTableNode& node, const std::string& synonymName);
	// Gets the count (number) of edges directly connecting synonym1 and synonym2
	int getCountOfAdjacentEdgesBetween(const std::string &synonym1, const std::string &synonym2);

	// Gets ALL indexes of the specified synEntityType, and the pkb to do the lookup
	std::vector<int>& getAllIndexes(DesignEntityType synEntityType, PKB *pkb);
	
	// Returns true if there is at least one node of the specified synonymName
	bool isThereAtLeastOneNodeOfSynonymName(const std::string& synonymName);

	// Checks, using the pkb, the given indexes vector for indexes which are of the specified synonymEntityType
	// and returns only those validated indexes in a vector
	std::vector<int>& validateIndexes(const std::vector<int>& indexes, DesignEntityType synonymEntityType, PKB *pkb);

	std::vector<int>& convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(int synonym1Value, DesignEntityType synonym1Type, DesignEntityType synonym2Type, PKB *pkb);

	// Removes all the elements in indexes that are not equal to theIndex.
	void leaveOnlyEqualIndexes(std::vector<int> *indexes, int theIndex);

	// Returns true if the specified relType has the same time complexity to find
	// out whether relType(1,x) is true/false and to get all the indices x of relType(1,x) that are true.
	bool isTimeConsumingRelationship(RelationshipType relType);

	/**-----------------------------------------------------------------------
	 * Helper functions for public updateWithNewRelationship function
	 *
	 *------------------------------------------------------------------------*/
	void updateWithNewRelationshipForEqualSynonyms(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
													PKB *pkb, SynonymTable *synonymTable);
	void updateWithNewRelationshipForBothSynonymsNotInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
													PKB *pkb, SynonymTable *synonymTable);
	void updateWithNewRelationshipForLeftSynonymInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
													PKB *pkb, SynonymTable *synonymTable);
	void updateWithNewRelationshipForRightSynonymInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
													PKB *pkb, SynonymTable *synonymTable);
	void updateWithNewRelationshipForBothSynonymsInTable(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, 
													PKB *pkb, SynonymTable *synonymTable);

	/**-----------------------------------------------------------------------
	 * Helper functions for public getTuples function
	 *
	 *------------------------------------------------------------------------*/
	// Ensure that synonym1 and synonym2 are related and different
	// and that the tablesMap given contains a table for synonym1.
	// This function traverses the graph starting from synonym1, for each of its nodes,
	// and aims to look for synonym2. Once it reaches synonym2, it will insert a tuple for synonym1
	// and synonym2 into the correct table as given in the tableMap (if it doesn't exist there,
	// then this creates a table and puts it there).
	void performTraversalForTupleFinding(const std::string& synonym1, const std::string& synonym2,
		std::unordered_map<std::string, SynonymResultsTable*> *tablesMap,
		const std::unordered_map<string, bool>& synonymsRequiredMap);
	// Takes table2 and for every row r1 in table1, 
	// appends (and duplicates if necessary) every row r2 from table2 onto it. 
	// table1 will be the resultant table of the merge at the end.
	void mergeTwoTupleTables(SynonymResultsTable *table1, const SynonymResultsTable& table2);
	// Checks if the edge e is a good edge for the node
	bool isGoodEdge(const ResultGraphTableNode& node, const edge& e);
	// Checks if the edge e is a bad edge for the node.
	bool isBadEdge(const ResultGraphTableNode& node, const edge& e);
	// Checks if the edge e is a bad edge for any of the given nodes which are of any synonym in the synonymsRequiredMap.
	bool isBadEdge(const std::vector<const ResultGraphTableNode*>& nodes, const edge& e, const std::unordered_map<string, bool>& synonymsRequiredMap);
	// Gets all the nodes that the specified node must use to check for bad edges
	std::vector<const ResultGraphTableNode*> getBadEdgeCheckingNodes(const ResultGraphTableNode& currentNode);
	// Finds and returns the synonym along the given pathmap that is nearest to the synonym2 and that exists in table1,
	// given also a synonym1 that is the start of the pathmap.
	std::string findNearestSynonym(const std::string& synonym1, const std::string& synonym2, 
		const PathMap& pathMap, const SynonymResultsTable& table1);
public:
	ResultGraphTable(void);
	~ResultGraphTable(void);

	/**
	 * Is this synonym in the graph-table?
	 * Returns true if yes, and false otherwise.
	 */
	bool isSynonymInTable(const std::string& synonym);
	/**
	 * Returns the list of result indexes for the specified synonym, of the specified synEntityType, using the specified PKB.
	 */
	std::vector<int>& getResultIndexesForSynonym(const std::string& synonym, DesignEntityType synEntityType, PKB *pkb);
	/**
	 * Returns the list of result nodes for the specified synonym, with which traversal through the graph-table can be done (e.g. for finding tuples).
	 */
	std::vector<ResultGraphTableNode>& getResultNodesForSynonym(const std::string& synonym);
	/**
	 * Performs the main algorithm and updating of the graph-table for the specified synonym1 and synonym2, 
	 * using the trueRelationshipPairs which are the pairs of synonym1 and synonym2 such that the relationship being evaluated holds.
	 * This is the function which will perform column insertion, link creation, graph traversal and link deletion.
	 * Returns false if there are no more nodes of either synonym1 or synonym2 in the table at the end of the update, and true otherwise.
	 */
	bool updateWithNewRelationship(const std::string& synonym1, const std::string& synonym2, RelationshipType relType, PKB *pkb, SynonymTable *synonymTable);
	/**
	 * Updates the graph-table for the specified synonym using the given badIndexesOfSynonym, which are the indexes of the given synonym which
	 * should be removed from the graph-table.
	 * If the synonym was not previously in the table, adds it to the table with all possible indexes first, using the pkb.
	 * Finally, looks through them and deletes those indexes which are bad (contained in badIndexesOfSynonym).
	 */
	bool updateSynonymWithBadResults(const std::string& synonym, std::vector<int>& badIndexesOfSynonym, PKB *pkb, SynonymTable *synonymTable);
	/** Updates the graph-table for the specified synonym using the given goodIndexesOfSynonym, which are the indexes of the given synonym which
	 * should be the only remaining indexes in the graph-table.
	 * If the synonym was not previously in the table, adds it to the table with all possible indexes first, using the pkb.
	 * Finally, looks through them and deletes those indexes which are not good (not contained in goodIndexesOfSynonym).
	 * NOTE: This method ends up calling updateSynonymWithBadResults, so calling updateSynonymWithBadResults immediately is faster.
	 */
	bool updateSynonymWithGoodResults(const std::string& synonym, std::vector<int>& goodIndexesOfSynonym, PKB *pkb, SynonymTable *synonymTable);
	/**
	 *	Searches the entire result graph table for the tuples of synonyms as specified in the synonymsRequiredMap.
	 *	Allocates memory and returns the reference to the table.
	 */
	Table<std::string, int>& getTuples(std::unordered_map<std::string, bool> synonymsRequiredMap, SynonymTable *synonymTable, PKB *pkb);
	/**
	 *	Returns the number of tuples of <synonym1, x, ... ,z, synonym2> in the graph, where synonym1 and synonym2 could have
	 *	many synonyms between them.
	 */
	int getEstimatedNumberOfTuples(const std::string &synonym1, const std::string &synonym2, DesignEntityType synType1, DesignEntityType synType2, PKB *pkb);
};